package br.com.sisop;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import Labirinto.Labirinto;
import Labirinto.Nodo;
import Labirinto.Posicao;

public class Dijkstra {

	private static final Integer PESO_DEFAULT = 1;

	private static Labirinto labirinto;
	private static Posicao posicaoEntrada;
	private static Posicao posicaoSaida;
	private static boolean finalizado;
	private static List<NodoDijkstra> prioridades;
	private static List<NodoDijkstra> posicoes;
	private static Queue<Posicao> fila;

	private static int custo = 0;
	private static int maxProfundidade;

	private static boolean debug = false;

	public Dijkstra(Labirinto labirinto) {
		new Dijkstra(labirinto, false);
	}

	@SuppressWarnings("static-access")
	public Dijkstra(Labirinto labirinto, boolean debug) {
		this.labirinto = labirinto;
		this.posicaoEntrada = labirinto.getPosicaoAtual();
		this.posicaoSaida = labirinto.getPosicaoSaida();
		this.finalizado = false;
		this.maxProfundidade = labirinto.getDimX() * labirinto.getDimY();

		this.prioridades = getPrioridades();
		this.posicoes = new ArrayList<NodoDijkstra>();
		this.fila = new LinkedList<Posicao>();
		this.debug = debug;

		fila.offer(posicaoEntrada);

		processaDijkstra();

		System.out.println("\nSOLUÇÃO COM ALGORITMO DIJKSTRA");
		System.out.println("------------------------------");
//		System.out.println("Posição Entrada : " + posicaoEntrada + "\nPosição Saída   : " + posicaoSaida);

		if (!(posicoes.isEmpty())) {
			Posicao[] menorCaminho = menorCaminho(posicoes);
			
			if (menorCaminho != null) {
				labirinto.print(menorCaminho);
			}
		} else {
			System.out.println("ATENÇÃO: Problema sem solução.\n");
		}
	}

	private Posicao[] menorCaminho(List<NodoDijkstra> teste) {
		if (posicaoSaida.comparaCom((Posicao) (teste.get(teste.size() - 1).getValor()))) {

			Nodo n = new Nodo(teste.get(teste.size() - 1).getPai(), teste.get(teste.size() - 1).getValor());

			Posicao[] caminho = new Posicao[teste.size()];
			int i = 0;

			while (n != null) {
				caminho[i] = (Posicao) n.getValor();
				i++;
				n = n.getPai();
			}
			
			int y = i;
			
			if (posicaoEntrada.comparaCom(caminho[y - 1])) {
				System.out.println("Solucao em: " + i + " passos.\n");
				
				Posicao[] result = new Posicao[i];
				
				for (int x = 0; x < i; x++) {
					result[x] = caminho[x];
				}
				
				return result;
			} else {
				System.out.println("ATENÇÃO: Problema sem solução.\n");
				return null;
			}
		} else {
			System.out.println("ATENÇÃO: Problema sem solução.\n");
			return null;
		}
	}

	public static void processaDijkstra() {
		if (debug) {
			System.out.println("ENTRADA");
			posicaoEntrada.print();
			System.out.println("-----");
			System.out.println("SAIDA");
			posicaoSaida.print();
			System.out.println("-----");
		}

		if (!(posicaoEntrada.comparaCom(posicaoSaida))) {
			processaNodo();
		}

		debug("Custo: " + custo);

		Posicao[] caminho = getPosicoesTabuleiro();

		if (debug) {
			labirinto.print(caminho);
		}

		for (NodoDijkstra n : prioridades) {
			debug(n + " - " + n.getPai());
		}
	}

	private static Posicao[] getPosicoesTabuleiro() {
		Posicao[] caminho = new Posicao[posicoes.size()];

		debug("POSICOES SIZE: " + posicoes.size());

		for (int i = 0; i < posicoes.size(); i++) {
			caminho[i] = (Posicao) posicoes.get(i).getValor();
		}

		return caminho;
	}

	private static void processaNodo() {
		Posicao posicao = fila.poll();
		List<Posicao> vizinhos = new ArrayList<Posicao>();

		if (posicao != null) {
			debug("NODO CENTRAL");

			vizinhos = labirinto.getExpansao(posicao);
			NodoDijkstra nodoCentral = getNodoByPrioridade(posicao);
			debug(nodoCentral);

			debug(nodoCentral.getProfundidade());
			debug("--------------------------");

			for (Posicao pos : vizinhos) {

				// debug("custo++");
				// custo++;

				NodoDijkstra nodo = getNodoByPrioridade(pos);

				if (!(nodo.isRemovido())) {
					fila.offer(pos);
				}

				debug(pos.getX() + " - " + pos.getY());

				if (nodo != null) {
					debug("antes: " + nodo.getProfundidade());

					if (nodo.getProfundidade() > nodoCentral.getProfundidade() + PESO_DEFAULT) {
						nodo.setPai(nodoCentral);
						nodo.setProfundidade(nodoCentral.getProfundidade() + PESO_DEFAULT);

						if (!(posicoes.contains(nodo))) {
							posicoes.add(nodo);
						}
					}

					debug("depois: " + nodo.getProfundidade());
					debug("---------");
				}

				if (posicaoSaida.comparaCom(pos)) {
					debug("FINALIZE");
					debug(pos);

					setFinalizado(true);
				}

				if (isFinalizado()) {
					break;
				}
			}
		}

		if (!(listaPrioridadesVazia()) && !(isFinalizado())) {
			debug("VIZINHOS:");
			debug(vizinhos);

			if (!(vizinhos.isEmpty())) {
				removePrioridades();
			}/* Adicionei essa porém alterou o resultado */else
				setFinalizado(true);

			processaNodo();
		}
	}

	private static boolean listaPrioridadesVazia() {
		List<NodoDijkstra> nodos = new ArrayList<NodoDijkstra>();

		for (NodoDijkstra nodo : prioridades) {
			if (!(nodo.isRemovido())) {
				nodos.add(nodo);
				break;
			}
		}

		debug("PRIORIDADES: " + nodos.size());

		return nodos.isEmpty();
	}

	private static void removePrioridades() {
		List<NodoDijkstra> nodos = getNodosRemocao();

		debug("NODOS REMOCAO");
		debug(nodos.size());

		for (NodoDijkstra nodo : nodos) {
			nodo.setRemovido(true);
			custo++;
		}
	}

	private static List<NodoDijkstra> getNodosRemocao() {
		List<NodoDijkstra> nodos = new ArrayList<NodoDijkstra>();

		int profundidade = defineProfundidadeRemocao();

		debug("PROFUNDIDADE: " + profundidade);

		if (profundidade < maxProfundidade) {
			for (NodoDijkstra nodo : prioridades) {
				if (nodo.getProfundidade() == profundidade
						&& !(nodo.isRemovido())) {
					nodos.add(nodo);
				}
			}
		}

		return nodos;
	}

	private static int defineProfundidadeRemocao() {
		int profundidade = maxProfundidade;

		for (NodoDijkstra nodo : prioridades) {
			if (profundidade > nodo.getProfundidade() && !(nodo.isRemovido())) {
				profundidade = nodo.getProfundidade();
			}
		}

		return profundidade;
	}

	private static NodoDijkstra getNodoByPrioridade(Posicao posicao) {
		NodoDijkstra nodo = null;

		for (NodoDijkstra n : prioridades) {
			Posicao pos = (Posicao) n.getValor();

			if (posicao.getX() == pos.getX() && posicao.getY() == pos.getY()) {
				nodo = n;
			}
		}

		return nodo;
	}

	private static List<NodoDijkstra> getPrioridades() {
		List<NodoDijkstra> nodos = new ArrayList<NodoDijkstra>();

		for (int i = 0; i < labirinto.getDimX(); i++) {
			for (int j = 0; j < labirinto.getDimY(); j++) {
				Posicao posicao = new Posicao(i, j);

				NodoDijkstra nodo = new NodoDijkstra(null, posicao);

				if (posicaoEntrada.getX() == i && posicaoEntrada.getY() == j) {
					nodo.setProfundidade(0);
				} else {
					nodo.setProfundidade(labirinto.getDimX()
							* labirinto.getDimY());
				}

				nodo.setRemovido(nodo.getProfundidade() == 0);
				nodos.add(nodo);
			}
		}

		return nodos;
	}

	public static boolean isFinalizado() {
		return finalizado;
	}

	public static void setFinalizado(boolean finalizado) {
		Dijkstra.finalizado = finalizado;
	}

	public static void debug(Object s) {
		if (debug) {
			System.out.println(s);
		}
	}

	public int getCusto() {
		return custo;
	}
}

class NodoDijkstra extends Nodo {

	private boolean removido;

	public NodoDijkstra(Nodo p, Object v) {
		super(p, v);
	}

	public boolean isRemovido() {
		return removido;
	}

	public void setRemovido(boolean removido) {
		this.removido = removido;
	}

	public String toString() {
		return getValor().toString() + " - " + getProfundidade()
				+ " Removido: " + removido;
	}

}
